Termination w.r.t. Q proof of TRS/TRCSREx1_GL02a

Termination w.r.t. Q of the following Term Rewriting System could be proven:

Q restricted rewrite system:
The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.

↳ QTRS

  ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.

Using Dependency Pairs [1,13] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:

A__EQ(s(X), s(Y)) → A__EQ(X, Y)
MARK(take(X1, X2)) → MARK(X2)
MARK(inf(X)) → MARK(X)
MARK(eq(X1, X2)) → A__EQ(X1, X2)
MARK(length(X)) → A__LENGTH(mark(X))
MARK(take(X1, X2)) → MARK(X1)
MARK(inf(X)) → A__INF(mark(X))
MARK(length(X)) → MARK(X)
MARK(take(X1, X2)) → A__TAKE(mark(X1), mark(X2))

The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ EdgeDeletionProof

Q DP problem:
The TRS P consists of the following rules:

A__EQ(s(X), s(Y)) → A__EQ(X, Y)
MARK(take(X1, X2)) → MARK(X2)
MARK(inf(X)) → MARK(X)
MARK(eq(X1, X2)) → A__EQ(X1, X2)
MARK(length(X)) → A__LENGTH(mark(X))
MARK(take(X1, X2)) → MARK(X1)
MARK(inf(X)) → A__INF(mark(X))
MARK(length(X)) → MARK(X)
MARK(take(X1, X2)) → A__TAKE(mark(X1), mark(X2))

The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We deleted some edges using various graph approximations

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ EdgeDeletionProof

        ↳ QDP

          ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

A__EQ(s(X), s(Y)) → A__EQ(X, Y)
MARK(take(X1, X2)) → MARK(X2)
MARK(eq(X1, X2)) → A__EQ(X1, X2)
MARK(inf(X)) → MARK(X)
MARK(length(X)) → A__LENGTH(mark(X))
MARK(take(X1, X2)) → MARK(X1)
MARK(inf(X)) → A__INF(mark(X))
MARK(length(X)) → MARK(X)
MARK(take(X1, X2)) → A__TAKE(mark(X1), mark(X2))

The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [13,14,18] contains 2 SCCs with 4 less nodes.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ EdgeDeletionProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

                ↳ QDPOrderProof

              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

A__EQ(s(X), s(Y)) → A__EQ(X, Y)

The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

A__EQ(s(X), s(Y)) → A__EQ(X, Y)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
A__EQ(x1, x2) = A__EQ(x2)
s(x1) = s(x1)

Recursive Path Order [2].
Precedence:

s₁ > A_{_EQ₁}

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ EdgeDeletionProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

                ↳ QDPOrderProof

                  ↳ QDP

                    ↳ PisEmptyProof

              ↳ QDP

Q DP problem:
P is empty.
The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ EdgeDeletionProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

                ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

MARK(take(X1, X2)) → MARK(X2)
MARK(inf(X)) → MARK(X)
MARK(take(X1, X2)) → MARK(X1)
MARK(length(X)) → MARK(X)

The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

MARK(take(X1, X2)) → MARK(X2)
MARK(take(X1, X2)) → MARK(X1)

The remaining pairs can at least be oriented weakly.

MARK(inf(X)) → MARK(X)
MARK(length(X)) → MARK(X)

Used ordering: Combined order from the following AFS and order.
MARK(x1) = MARK(x1)
take(x1, x2) = take(x1, x2)
inf(x1) = x1
length(x1) = x1

Recursive Path Order [2].
Precedence:

[MARK₁, take_2]

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ EdgeDeletionProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

                ↳ QDPOrderProof

                  ↳ QDP

                    ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

MARK(inf(X)) → MARK(X)
MARK(length(X)) → MARK(X)

The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

MARK(inf(X)) → MARK(X)

The remaining pairs can at least be oriented weakly.

MARK(length(X)) → MARK(X)

Used ordering: Combined order from the following AFS and order.
MARK(x1) = MARK(x1)
inf(x1) = inf(x1)
length(x1) = x1

Recursive Path Order [2].
Precedence:

[MARK₁, inf_1]

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ EdgeDeletionProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

                ↳ QDPOrderProof

                  ↳ QDP

                    ↳ QDPOrderProof

                      ↳ QDP

                        ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

MARK(length(X)) → MARK(X)

The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

MARK(length(X)) → MARK(X)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
MARK(x1) = x1
length(x1) = length(x1)

Recursive Path Order [2].
Precedence:

trivial

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ EdgeDeletionProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

                ↳ QDPOrderProof

                  ↳ QDP

                    ↳ QDPOrderProof

                      ↳ QDP

                        ↳ QDPOrderProof

                          ↳ QDP

                            ↳ PisEmptyProof

Q DP problem:
P is empty.
The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.